package interview

func subMaxCount(nums []int) int {
	dp := make([]int, len(nums))

	if len(nums) == 0 {
		return 0
	} else if len(nums) == 1 {
		if nums[0] > 0 {
			return nums[0]
		} else {
			return 0
		}
	}
	dp[0] = maxInt(nums[0], 0)
	for i := 1; i < len(nums); i++ {
		if dp[i-1] > 0 {
			dp[i] = maxInt(dp[i-1]+nums[i], 0)
		} else {
			dp[i] = maxInt(nums[i], 0)
		}
	}
	max := dp[0]
	for _, num := range dp {
		max = maxInt(max, num)
	}
	return max
}

func maxInt(x, y int) int {
	if x > y {
		return x
	}
	return y
}
